package com.fr.lintcode;

public class Q221 {

    /**
     * @param l1:
     *            The first list.
     * @param l2:
     *            The second list.
     * @return: the sum list of l1 and l2.
     */
    public ListNode addLists2(ListNode l1, ListNode l2) {
        // write your code here
        ListNode l11 = reverse(l1);
        ListNode l22 = reverse(l2);
        ListNode rs = null;
        int add = 0;
        while (l11 != null && l22 != null) {
            int sum = l11.val + l22.val + add;
            if (sum >= 10) {
                add = 1;
                sum = sum - 10;
            } else {
                add = 0;
            }
            ListNode tmp = new ListNode(sum);
            tmp.next = rs;
            rs = tmp;
            l11 = l11.next;
            l22 = l22.next;
        }
        while (l11 != null) {
            int sum = l11.val + add;
            if (sum >= 10) {
                add = 1;
                sum = sum - 10;
            } else {
                add = 0;
            }
            ListNode tmp = new ListNode(sum);
            tmp.next = rs;
            rs = tmp;
            l11 = l11.next;
        }
        while (l22 != null) {
            int sum = l22.val + add;
            if (sum >= 10) {
                add = 1;
                sum = sum - 10;
            } else {
                add = 0;
            }
            ListNode tmp = new ListNode(sum);
            tmp.next = rs;
            rs = tmp;
            l22 = l22.next;

        }
        if (add > 0) {
            ListNode tmp = new ListNode(add);
            tmp.next = rs;
            rs = tmp;
        }
        return rs;
    }

    private ListNode reverse(ListNode node) {
        ListNode tmp = node;
        ListNode head = null;
        while (tmp != null) {
            ListNode tmp1 = tmp.next;
            tmp.next = head;
            head = tmp;
            tmp = tmp1;
        }
        return head;
    }
}
